package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-04-01 14:57
 */
public class BI954二倍数对数组 {

    public static void main(String[] args) {
        int[] arr = {2,4,8,1};

        System.out.println(canReorderDoubled(arr));
    }


    /**
     * 从第一个数字开始遍历 寻找自己的两倍数或半数 将其放在一个组 继续遍历 判断每个组的数量是否是偶数 如果存在非偶数的 则返回false
     *
     * 优化：使用map代替遍历查找
     * @param arr
     * @return
     */
    public static boolean canReorderDoubled(int[] arr) {
        //Arrays.sort(arr);

        boolean[] arrFlag = new boolean[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if (arrFlag[i]) {
                continue;
            }
            for (int j = i + 1; j < arr.length; j++) {
                if (arrFlag[j]) {
                    continue;
                }
                if (arr[i] > 0) {
                    if (arr[j] == arr[i] << 1) {
                        arrFlag[i] = true;
                        arrFlag[j] = true;
                        break;
                    }
                } else {
                    if (arr[j] << 1 == arr[i]) {
                        arrFlag[i] = true;
                        arrFlag[j] = true;
                        break;
                    }
                }

            }
            if (!arrFlag[i]) {
                return false;
            }
        }
        return true;
    }
}
